1. Field of the Invention
This invention relates to transform coding for digital signals, and more particularly to coding of picture signals.
2. Description of the Related Art
Conventionally, a linear transform coding system is known as a coding system for an audio or video signal. In the linear transform coding system, a plurality of discrete signals are linearly transformed collectively and resulting transform coefficients are coded, and compression coding can be achieved by selecting the base of the transform taking statistical characters of the signal into consideration. It is known that a coding system which employs discrete cosine transform for the linear transform can realize high compression coding for a signal which behaves in accordance with a Markovian model, and is utilized widely for international standardized systems.
While the discrete cosine transform is useful for realization of high compression coding, since the base of the transform is a real number, it is disadvantageous in that, in order to realize reversible coding, the quantization step size must be small, which results in deterioration of the coding efficiency.
A system which realizes reversible coding of discrete cosine transform without deterioration of the coding efficiency has been proposed by the inventor of the invention of the present application. The system modifies the discrete cosine transform so as to allow reversible transform. The system has two characteristics: one is to approximate the discrete cosine transform with linear transform with an integer matrix, and the other is to remove redundancies included between transform coefficients by reversible quantization.
In the following, a principle of eight-element reversible cosine transform according to the system described above is described. The original eight-element discrete cosine transform according to the international standards transforms an original signal vector (x0, x1, . . . , x7) into transform coefficients (X0, X1, . . . , X7) in accordance with the following expression (1): ##EQU1## where c1, . . . , c7 are represented by the following expression (2): ##EQU2##
In this eight-element reversible discrete cosine transform, the eight-element discrete cosine transform represented by the expression (1) is approximated with a transform of the following expression (3): ##EQU3## where a1, . . . , a7 are natural numbers. The values a1, . . . , a7 are obtained by multiplying each row vector of the discrete cosine transform by a certain number and rounding the products into integers. (X0, . . . , X7) obtained based on the expression (3) have values near to the original discrete cosine transform coefficients except that they are multiplied by the certain number.
However, the transform coefficients X0, . . . , X7 obtained based on the expression (3) are not independent of each other, but have redundancies. Where the absolute value of the determinant of a transform matrix is represented by D, the density of points which may be taken in the transform domain is 1/D. In other words, the ratio of the points which may be taken in the transform region from among all integer lattice points is 1/D, and the remaining points of the ratio 1-1/D are wasteful points which cannot be taken actually. To use those wasteful points also as an object for coding makes a cause of decreasing the efficiency of compression coding.
Thus, in order to remove the redundancies, reversible coding is performed. However, since it is difficult to define a reversible transform directly in an eight-element space, the expression (3) is decomposed in accordance with a fast calculation scheme and reversible quantization is performed for results of the individual partial transforms.
The transform of the expression (3) can be decomposed into the following expressions (4) to (10): ##EQU4## It is to be noted that, in the expression (10), a4=1. This is because the matrix of the expression (10) only includes a4 and there is no problem if it is assumed that a4=1. In this manner, the expression (3) can be decomposed into eight 2.times.2 matrix transforms and one 4.times.4 matrix transform. Redundancies are produced in the individual transforms. For example, in the transform of the expression (4), since the absolute value of the determinant of the transform matrix is 2, integer vector values which may possibly be taken as a transform results are 1/2 the entire integer vector values. The redundancies produced in the individual transforms in this manner are removed for the individual transforms. To this end, for each transform, a result of the transform is reversibly transformed as seen in FIG. 22. Referring to FIG. 22, reference numerals 160 to 167 denote each a transformer for a 2.times.2 matrix, and 168 denotes a transformer for a 4.times.4 matrix.
Here, comparison between an eight-element a reversible discrete cosine transform and the original discrete cosine transform is described. Similarly as in FIG. 22, also the original eight-element discrete cosine transform can be decomposed as seen in FIG. 24. In FIG. 24, transform matrices of individual 2.times.2 and 4.times.4 transforms are normalized so that they may correspond to those in FIG. 22. From comparison between FIGS. 22 and 24, it can be seen that the transformer 160 and a transformer 180, the transformer 161 and a transformer 181, the transformer 162 and a transformer 182, the transformer 163 and a transformer 183, the transformer 164 and a transformer 184, the transformer 165 and a transformer 185, the transformer 166 and a transformer 186, the transformer 167 and a transformer 187, and the transformer 168 and a transformer 188 correspond to each other. If results obtained by the corresponding transforms are equal, then also transform coefficients obtained finally have substantially equal values. As hereinafter described, this is important when the compatibility between an eight-element reversible discrete cosine transform and the original eight-element discrete cosine transform is considered. It is to be noted that, as can be seen from the comparison between the transforms, the portion of the discrete cosine transform which corresponds to normalization of the base is replaced by reversible quantization in the reversible discrete cosine transform. Consequently, it is important how to make a result of reversible quantization approach a result of normalization in order to achieve the compatibility. Subsequently, the reversible quantization is described in regard to a case of transform by a 2.times.2 matrix and another case of transform by a 4.times.4 matrix.
In a transform by a 2.times.2 matrix, transform points obtained by transforming integer lattice points are reversibly quantized making use of the periodicity of the structure of them. Where the absolute value of the determinant of a transform matrix is represented by D and the coordinates of a transform point obtained by transforming an integer vector are represented by (Y1, Y2), it can be proved that the structure of all of such transform points (Y1, Y2) has the period D in the direction of each axis. Therefore, a region represented by the following expression (13) EQU {(Y.sub.1, Y.sub.2).vertline.0.ltoreq.Y.sub.1 .ltoreq.N.sub.1 -1, 0.ltoreq.Y.sub.2 .ltoreq.N.sub.2 -1} (13)
(where N1 and N2 are multiples of D, and they are each hereinafter referred to as quantization period) is determined as a basic region, and quantization values of transform points included in the basic region are artificially defined in advance. Then, the correspondence between the transform points and the quantization values is described in the form of and held as a table (this table is hereinafter referred to as quantization correspondence table), and quantization is performed using this table as described below.
An actual procedure of quantization is such as follows. First, quotients b1, b2 and remainders r1, r2 when the coordinates Y1, Y2 of the transform points are divided by the quantization periods N1, N2, respectively. Thus, the remainders (r1, r2) are included in the basic region provided by the expression (13). Then, using the quantization correspondence table defined as above, quantization values (q1, q2) (hereinafter referred to as local quantization) of (r1, r2) are calculated. Then, quantization values (Yq1, Yq2) of (Y1, Y2) are calculated from the quotients b1, b2 and the local quantization values q1, q2 in accordance with the following expressions (14): ##EQU5## where M1, M2 are natural numbers and represent dynamic ranges of q1, q2, respectively. The values M1 and M2 represent the magnitudes of the basic region when measured with a scale of the quantization values.
The dynamic ranges M1, M2 represent the periods of dequantization described below (therefore, M1, M2 are hereinafter referred to as dequantization periods).
Now, dequantization of a 2.times.2 matrix transform is described. Also dequantization can be performed in a procedure similar to that for quantization. First, quantization values Yq1, Yq2 are divided by the dequantization periods M1, M2 described above to obtain quotients b1', b2' and remainders q1' and q2', respectively. Then, a table (hereinafter referred to as dequantization correspondence table) which describes a correspondence relationship reverse to that of the quantization correspondence table is referred to obtain (r1', r2') corresponding to (q1', q2'). Then, dequantization values (Y1, Y2) are calculated in accordance with the following expression (15): ##EQU6## Quantization and dequantization of a 2.times.2 matrix transform are such as described above.
(X1, X7, X3, X5) obtained by transform of a 4.times.4 matrix given by the following expression (16) are divided into (X1, X7) and (X3, X5), for which quantization is performed separately. ##EQU7## where (u4, u5, u6, u7) are an integer vector. A construction of the conventional 4.times.4 reversible transformer which realizes a transform of the expression (16) and such 4.times.4 reversible dequantization is shown in FIG. 26.
The transform coefficients (X1, X7) are linearly quantized with the step sizes k1, k7 (k1 and k7 are natural numbers) by linear quantizers 4, 5, respectively. The values of the quantization step sizes k1, k7 are set so that the dynamic ranges of quantization values (Xq1, Xq7) of (X1, X7) and quantization values (Xq3, Xq5) of (X3, X5) may be nearly equal to each other.
On the other hand, for quantization of the transform coefficients (X3, X5), the relationship described below is utilized. In particular, the relationship that, once (X1, X7) are determined, a certain integer vector (s3, s5) is determined and the values which may possibly be taken by (X3, X5) are limited to the following expression (17) is utilized: ##EQU8## where g, h are integers represented, from a1, a3, a5 and a7 of the expression (16), as ##EQU9## Points which may possibly be taken by transform coefficients (X3, X5) represented by the expression (17) are shown in FIG. 28. In this manner, the structure of all of the values which may possibly be taken by the transform coefficients (X3, X5) when certain (X1, X7) are determined is equivalent to a lattice structure defined by vectors (h, g), (-g, h) which is displaced by the integer vector (s3, s5) (hereinafter referred to as representative elements).
Further, when the transform coefficients X1, X7 are linearly quantized with the step sizes k1, k7 as described above, respectively, the structure of values which may be taken by (X3, X5) is a structure wherein k1k7 such lattices as shown in FIG. 28 overlap with each other. This is because the number of transform coefficients (X1, X7) which may be rounded to one quantization values (Xq1, Xq7) is k1k7, and representative elements (s3, s5) correspond to each of the k1k7 transform coefficients. Since only the portion of the representative elements (s3, s5) in the expression (17) varies depending upon the values of (X1, X7), the set of all of points which may be taken by the transform coefficients (X3, X5) when X1, X7 are linearly quantized with the step sizes k1, k7, respectively, is equivalent to the lattice structure of the expression (17) which overlaps at the k1k7 transform coefficients but is different only in a manner of displacement. For example, when k1=k7=2, points which may be taken by the transform coefficients (X3, X5) are such as illustrated in FIG. 29. As can be seen from FIG. 29, the structure of points which may possibly be taken by the transform coefficients (X3, X5) exhibits a repetition of the same pattern for each period defined by the vectors (h, g), (-g, h). Therefore, the points are divided into groups each of which includes points whose global signal values (p3, p5) are equal to each other, and quantization is performed for each of the groups. Then, in each group, the global signal (p3, p5) which has an equal value in the group and representative elements (s3, s5) which are different for individual points in the group are quantized separately, and then resulting quantized values are added to calculate a quantized value. Subsequently, description is given of the quantization.
First, a procedure of calculating quantization values (pq3, pq5) of global signals (p3, p5) is described. The structure of all of points which may possibly be taken by the global signals (p3, p5) includes transform points obtained by transforming, from the expression (17), integer lattice points with the matrix ##EQU10## Therefore, for the global signals (p3, p5), reversible quantization performed in the 2.times.2 matrix transform described above is performed. First, in order to obtain the global signals (p3, p5), representative elements (s3, s5) are determined from values of transform coefficients X1, X7 based on a first numeric table 201. Details are hereinafter described. Next, s3, s5 are subtracted from X3, X5 to obtain global signals p3, p5 by adders 14, 15, respectively. Then, the aforementioned 2.times.2 reversible quantization based on the matrix of the expression (19) is performed by a transformer 202. Results of the 2.times.2 revisable quantization are multiplied by m3, m5 by multipliers 204 and 205 to calculate global quantization values (pq3, pq5). Here, m3, m5 represent dynamic ranges of the local quantization values sq3, sq5, respectively.
Subsequently, a procedure of calculating the quantization values (sq3, sq5) of the representative elements (s3, s5) is described. This does not directly calculate the quantization values from values of the representative elements (s3, s5), but determines the quantization values using a second numeric table 203 from quantization residuals (r1, r7) of the transform coefficients (X1, X7) represented by the following expression (20): ##EQU11##
Then, adders 16 and 17 add the local quantization values sq3, sq5 to the global quantization values pq3, pq5 to obtain quantization values (Xq3, Xq5), respectively. By the processing described above, all quantization values (Xq1, Xq7, Xq3, Xq5) are obtained.
Subsequently, a procedure of calculating the representative elements (s3, s5) from the values of the transform coefficients (X1, X7) based on the first numeric table 201 of FIG. 26 is described. The values of the representative elements (s3, s5) vary depending upon the values of the transform coefficients (X1, X7). However, where the values of g, h are given by the expression (18), if the remainders when components of the vector (gX1+hX7, gX7-hX1) are divided by the determinant of the matrix of the expression (19) EQU D4=g.sup.2 +h.sup.2 (21)
are equal to each other, then also the representative elements (s3, s5) are equal. In other words, where the remainder when x is divided by y is represented by mod(x, y), the representative elements (s3, s5) vary depending upon the value of the vector EQU z(X.sub.1, X.sub.7)=(mod(gX.sub.1 +hX.sub.7, D.sub.4), mod(gX.sub.7 -hX.sub.1, D.sub.4)) (22)
Thus, in the first numeric table, the correspondence relationship between the vector z(X1, X7) and the representative elements (s3, s5) is described. Then, the value of the vector z(X1, X7) of the expression (22) is calculated first, and then referring to the first numeric table 201 of FIG. 26, the representative elements (s3, s5) are determined from the value of the vector z(X1, X7). Particularly if g and h are prime relative to each other, then if one of two components ##EQU12## of the vector z(X1, X7) is determined, then the representative elements (s3, s5) can be determined without determining the other components. Accordingly, in this instance, (s3, s5) can be determined by describing the corresponding relationship between one of two components of each of z1(X1, X7), z1(X1, X7) of the expression (23) and the representative elements (s3, s5) in the first numeric table.
Subsequently, a procedure of calculating the local quantization values (sq3, sq5) from the quantization residuals (r1, r7) based on the second numeric table 203 is described. First, local quantization of the transform coefficients (X3, X5) is described, and then a procedure of calculating (s3, s5) using the quantization residuals (r1, r7) is described.
As described above, when the transform coefficients X1, X7 are linearly quantized with the step sizes k1, k7, a resulting structure includes such k1k7 overlapping lattice point structures as represented by the expression (17) as seen in FIG. 29. Local quantization of the transform coefficients (X3, X5) groups k1k7 points whose global signals (p3, p5) are same into a group and allocates different quantization values (sq3, sq5) to representative elements of the k1k7 points. Quantization from the representative elements (s3, s5) into the local quantization values (sq3, sq5) can be realized by referring to a table prepared so as to describe the correspondence between them. However, since the set of values which may possibly be taken by the representative elements (s3, s5) depends upon the values of (Xq1, Xq7), a plurality of tables each describing such a correspondence are required. However, if the values of the representative elements (s3, s5) for the quantization representative values (X1, X7)=(k1Xq1, k7Xq7) are equal, then also the values of the representative elements (s3, s5) for the other (k1k7-1) different (X1, X7) in the same group coincide with them. Consequently, in this instance, a same correspondence table can be used. Accordingly, the number of those correspondence tables which must be prepared is a number equal to the number of values which may possibly be taken by (s3, s5). This value is equal to or smaller than D4. Then, a table is selected based on the representative elements (s3, s5) for the quantization representative values (k1Xq1, k7Xq7) and used for quantization.
Here, for such selection of a table, in place of the values of the representative elements (s3, s5) for the quantization representative values (k1Xq1, k7Xq7), the values of the expression (22) for the quantization representative values, that is, the values of the vector z(k1X1, k7X7) may be used. In other words, a table can be selected using the values of the vector z(k1X1, k7X7) as an index. By this, a table can be selected directly without calculating the values of the representative values for the quantization representative values using the first numeric table. It is to be noted that, if g and h are prime relative to each other, then only one of components z1(k1X1, k7X7) and z2(k1X1, k7X7) of the vector z(k1X1, k7X7) may be used as an index.
Further, in order to calculate the local quantization values (sq3, sq5), the quantization residuals (r1, r7) represented by the expression (20) may be used in place of the quantization representative values (s3, s5). This is because, if (Xq1, Xq7) is determined, then also the correspondence between (X1, X7) and (r1, r7) is determined. Since the set of values which may possibly be taken by the representative values (s3, s5) is different depending upon the quantization values (Xq1, Xq7), where the local quantization values (sq3, sq5) are determined directly from the representative elements (s3, s5), also the values of the representative values (s3, s5) must necessarily be written in the table. In contrast, since the set of values which may possibly be taken by the quantization residuals (r1, r7) does not depend upon the quantization values (Xq1, Xq7), this information need not be held. Therefore, the table may have a reduced size.
Subsequently, dequantization of a 4.times.4 matrix transform is described. First, a construction of a 4.times.4 inverse transformer of the system proposed by the inventor of the inventor of the present application is shown in FIG. 27. Referring to FIG. 27, in the 4.times.4 inverse transformer, quantization values (Xq1, Xq7, Xq3, Xq5) are dequantized to obtain (X1, X7, X3, X5), and then the dequantization values (X1, X7, X3, X5) are inverse transformed as given by the following expression (24) inverse to the expression (16) to obtain an integer vector (u4, u5, u6, u7). ##EQU13##
Subsequently, the dequantization from the quantization values (Xq1, Xq7, Xq3, Xq5) to the transform coefficients (X1, X7, X3, X5) is described. Also this is performed separately for (Xq1, Xq7) and (Xq3, Xq5).
The quantization values (Xq1, Xq7) are first multiplied by k1, k7 by multipliers 34, 35 to obtain quantization representative values (k1Xq1, k7Xq7), respectively. Then, quantization residuals (r1, r7) are added to the quantization representative values (k1Xq1, k7Xq7) by adders 36, 37 to calculate (X1, X7), respectively. The quantization residuals (r1, r7) are calculated from local quantization values (sq3, sq5) calculated by a procedure which will be hereinafter described using a third numeric table 211. The third numeric table 211 is a table which describes correspondences reverse to those of the second numeric table of FIG. 26. Then, similarly as in the reversible transformer of FIG. 26, when the third numeric table 211 is to be referred to, the values of the vector z(X1, X7) of the expression (22) for the quantization representative values (k1Xq1, k7Xq7), that is, the values of the vector z(k1Xq1, k7Xq7), are used as an index. It is to be noted that, also in this instance, if g and h are prime relative to each other, then only one of two components z1(k1Xq1, k7Xq7) and z2(k1Xq1, k7Xq7) of the vector z(k1Xq1, k7Xq7) may be used as an index.
Meanwhile, the quantization values Xq3, Xq5 are first divided by m3, m5 by integer dividers 212, 213 to obtain quotients pq3, pq5 and remainders sq3, sq5, respectively. Once the local quantization values (sq3, sq5) are calculated, transform coefficients (X1, X7) can be calculated as described above. Then, a dequantizer 210 dequantizes the quotients (pq3, pq5) based on the matrix of the expression (19) to obtain global signals (p3, p5). Then, from the transform coefficients (X1, X7) calculated already, representative elements (s3, s5) are determined using a fourth numeric table 214 equivalent to the first numeric table 201 of FIG. 26. Adders 38, 39 add the global signals (p3, p5) to the representative elements (s3, s5) to obtain transform coefficients (X3, X5), respectively. By the procedure described above, dequantization is completed and the transform coefficients (X1, X7, X3, X5) are obtained. Quantization and dequantization of a 4.times.4 matrix transform are such as described above.
By performing reversible quantization of a 2.times.2 or 4.times.4 matrix transform described above after each transform of the expressions (4) to (12) as seen in FIG. 22, redundancies included in results of transform can be removed. As a result, reversible coding can be realized without deteriorating the coding efficiency. Further, by suitably adjusting the quantization period Ni and the dequantization period Mi, transform coefficients of eight-element reversible discrete cosine transform obtained finally can be made to approach those of the original discrete cosine transform.
One of problems of the conventional eight-element reversible discrete cosine transform described above resides in that it is not sufficiently compatible with the original eight-element discrete cosine transform. In particular, the quality of a reproduction signal obtained when a signal coded using eight-element reversible discrete cosine transform is decoded using the original eight-element inverse discrete cosine transform or when reverse decoding is performed is not sufficiently high.
The reason is that the differences (hereinafter referred to as errors) between transform coefficients of the conventional eight-element reversible discrete cosine transform and transform coefficients of the original eight-element discrete cosine transform are not small. This arises from the fact that the differences between Xq1, Xq7, Xq3, Xq5 obtained by 4.times.4 reversible quantization by the transformer 168 of FIG. 22 and X1, X7, X3, X5 obtained by transform by the transformer 188 shown in FIG. 24 are not small. While the errors of the transform coefficients may be caused by three different factors including errors originating from a difference in dynamic range, errors originating from quantization which uses a table and approximate errors caused by integer transform, in the conventional reversible quantization based on a 4.times.4 matrix transform described above, global quantization of (X3, X5) is performed using a table as described above, and then resulting values are multiplied by m3, m5 as seen from FIG. 26. As a result, quantization errors arising from use of the table are amplified to m3, m5 times, thereby increasing the errors.